package org.basis.algorithm.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 打印字符串所有的全排列
 *
 * @author Mr_wenpan@163.com 2021/12/28 11:06
 */
public class PrintAllPermutations {


    public static void main(String[] args) {
        process("abcd");
    }

    public static void process(String word) {
        if (word == null) {
            return;
        }
        List<String> list = new ArrayList<>();
        doProcess(word.toCharArray(), 0, list);
        System.out.println(list.size());
        System.out.println(list);
    }

    public static void doProcess(char[] chars, int index, List<String> result) {
        if (index >= chars.length) {
            // 收集结果
            result.add(new String(chars));
        }
        // 剪枝操作，记录某个字符是否看过，去重
        boolean[] visited = new boolean[26];
        for (int i = index; i < chars.length; i++) {
            int idx = chars[i] - 'a';
            // 如果之前没有这个字符被交换到该位置，则交换过来
            if (!visited[idx]) {
                visited[idx] = true;
                // 把i位置的字符和index位置的字符进行换位
                swap(chars, i, index);
                // 交换完后去看有多少种结果
                doProcess(chars, index + 1, result);
                // 交换回来
                swap(chars, i, index);
            }
        }
    }

    private static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
